head = {
  val: 1,
  next: {
    val: 2,
    next: {
      val: 3,
      next: {
        val: 4,
        next: null
      }
    }
  }
}


// head.val
// head.next.val
// head.next.next.val
// head.next.next.next.val


// function ListNode(val) {
//   this.val = val;
//   this.next = null;
// }

// const node = new ListNode(1)
// node.next = new ListNode(2)
// node.next.next = new ListNode(3)


// const index = 10
// let node = head
// for (let i = 0; i < index && node; i++) {
//   console.log(node.val)
//   node = node.next
// }

let Node = function (val) {
  this.val = val
  this.next = null
}

var MyLinkedList = function () {
  this.head = null
  this.size = 0
};

/** 
 * @param {number} index
 * @return {number}
 */
MyLinkedList.prototype.get = function (index) {
  if (index < 0 || index >= this.size) return -1
  let cur = this.head
  for (let i = 0; i < index; i++) {
    cur = cur.next
  }

  return cur.val
};

/** 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtHead = function (val) {
  let newNode = new Node(val)
  newNode.next = this.head
  this.head = newNode
  this.size++
};

/** 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtTail = function (val) {
  let newNode = new Node(val)
  if (!this.head) {
    this.head = newNode
  } else {
    let cur = this.head
    while (cur.next) {
      cur = cur.next
    }
    cur.next = newNode
  }
  this.size++

};

/** 
 * @param {number} index 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtIndex = function (index, val) {
  if (index < 0 || index > this.size) return false
  if (index === 0) {  // 头部添加
    this.addAtHead(val)
  } else {
    let newNode = new Node(val)
    let cur = this.head
    for (let i = 0; i < index - 1; i++) {
      cur = cur.next
    }
    newNode.next = cur.next
    cur.next = newNode
  }

  this.size++
};

/** 
 * @param {number} index
 * @return {void}
 */
MyLinkedList.prototype.deleteAtIndex = function (index) {
  if (index < 0 || index >= this.size) return
  if (index === 0) {
    this.head = this.head.next
  } else {
    let cur = this.head
    for (let i = 0; i < index - 1; i++) {
      cur = cur.next
    }
    if (cur.next) {
      cur.next = cur.next.next
    }
  }
  this.size--
};

MyLinkedList.prototype.travser = function () {
  let cur = this.head
  while (cur) {
    console.log(cur.val);
    cur = cur.next
  }
};


var myLinkedList = new MyLinkedList()
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
myLinkedList.travser()
console.log(myLinkedList.get(1));// 返回 2
myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3
// myLinkedList.get(1);              // 返回 3
// myLinkedList.travser()
// console.log(obj.get(0));



/** 
 * Your MyLinkedList object will be instantiated and called as such:
 * var obj = new MyLinkedList()
 * var param_1 = obj.get(index)
 * obj.addAtHead(val)
 * obj.addAtTail(val)
 * obj.addAtIndex(index,val)
 * obj.deleteAtIndex(index)
 */